package nowcoder.interview;

import java.util.ArrayList;
import java.util.HashSet;

class Solution {
    HashSet<String> set = new HashSet<>();

    public String[] permutation(String S) {

        dfs(S.toCharArray(), 0);
        return new ArrayList<String>(set).toArray(new String[0]);
    }

    private void dfs(char[] charArray, int k) {
        if (k == charArray.length) {
            set.add(new String(charArray));
            return;
        }
        for (int i = k; i < charArray.length; i++) {
            String o = String.valueOf(charArray);
            if (!set.contains(o)) {
                set.add(o);
                swap(charArray, i, k);
                dfs(charArray, k + 1);
                swap(charArray, i, k);
            }

        }
    }

    public void swap(char[] c, int x, int y) {
        char temp = c[x];
        c[x] = c[y];
        c[y] = temp;
    }

}